package leetcode.editor.cn;

import utils.TreeNode;

/**
 * 打家劫舍 III
 * @author qulq
 * @date 2024-07-28 09:00:04
 */
public class T337_HouseRobberIii{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T337_HouseRobberIii().new Solution();
	 }
	/**
	 * 如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子
	 * f[i]表示：节点node为根节点能偷到的最大金额
	 * f[1]：不偷 、 f[2]：偷
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
		int[] dp = recursion(root);
		return Math.max(dp[0], dp[1]);
    }

	public int[] recursion(TreeNode root) {
		int[] dp = new int[2];
		if (root == null) {
			return dp;
		}
		int[] left = recursion(root.left);
		int[] right = recursion(root.right);

		// 不偷根节点，可以考虑偷左右孩子
		dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
		// 偷根节点
		dp[1] = root.val + left[0] + right[0];
		return dp;

	}

}
//leetcode submit region end(Prohibit modification and deletion)

}